package com.kavinz.algo.string.sort;

/**
 * Sedgewick and Wayne, Algorithms (4th edition) Exercises 5.1.2:Give a trace
 * for LSD string sort for the
 * keys"no is th ti fo al go pe to co to th ai of th pa"
 * 
 * @author kevinzhao
 */
public class FixedLengthLSD {
	private int N;// length of each String key
	private int R;// R-character alphabet

	private void sort(VO vo) {
		String[] inputArray = vo.keys.split(",");
		this.N = vo.N;
		this.R = vo.R;
		// we will do N times loop here,which is the length of the key
		for (int i = N - 1; i >= 0; i--) {
			int[] count = new int[R];
			String[] aux = new String[R];
			// 1.Compute frequency count
			for (String key : inputArray) {
				// Sort each char of the key string each time
				if (key == null)
					continue;
				char keyChar = key.charAt(i);
				// Increments the count[r+1]
				count[keyChar + 1]++;
				// count[keyChar]++;
			}
			// System.out.println("after count:" + this.showIntArray(count));
			// 2.Transform count[] to indices[]
			for (int j = 0; j < R - 1; j++) {
				// transform
				count[j + 1] += count[j];
			}
			// System.out.println("after transforming to indices:"
			// + this.showIntArray(count));

			// 3.distribute
			for (String key : inputArray) {
				// Sort each char of the key string each time
				if (key == null)
					continue;
				char keyChar = key.charAt(i);

				aux[count[keyChar]] = key;
				count[keyChar]++;
			}

			// 4.Copy back
			int inputArrayIndex = 0;
			for (int k = 0; k < aux.length; k++) {

				if (aux[k] != null)
					inputArray[inputArrayIndex++] = aux[k];
			}
		}
		System.out.println("complete:" + this.showStringArray(inputArray));
	}

	public static void main(String[] args) {
		FixedLengthLSD sorter = new FixedLengthLSD();
		FixedLengthLSD.VO vo1 = sorter.new VO(2, 122,
				"no,is,th,ti,fo,al,go,pe,to,co,to,th,ai,of,th,pa");// ASCII
																	// value of
																	// letter z
																	// is 122
		FixedLengthLSD.VO vo2 = sorter.new VO(1, 122,
				"1,2,2,2,4,9,8,6,1,3,4,7,9,6");

		FixedLengthLSD.VO vo3 = sorter.new VO(1, 122, "1,8,5,3,8,5,8,5,1");

		FixedLengthLSD.VO vo4 = sorter.new VO(
				7,
				122,
				"4PGC938,1ICK750,2IYE230,1ICK750,3CIO720,1OHV845,1ICK750,1OHV845,1OHV845,1OHV845,4JZY524,2IYE230,1ICK750,2RLA629,3CIO720,2RLA629,1OHV845,3ATW723,1OHV845,3CIO720,2RLA629,3CIO720,2RLA629,4JZY524,3ATW723");
		sorter.sort(vo4);
	}

	/**
	 * show the data of the specified array
	 * 
	 * @param array
	 * @return
	 */
	private String showIntArray(int[] array) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < array.length; i++) {
			sb.append(Character.toChars(i)).append("=").append(array[i])
					.append(",");
		}
		return sb.toString();
	}

	private String showStringArray(String[] array) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < array.length; i++) {
			sb.append(array[i]).append(",");
		}
		return sb.toString();
	}

	class VO {
		int N;
		int R;
		String keys;

		public VO(int N, int R, String keys) {
			this.N = N;
			this.R = R;
			this.keys = keys;
		}
	}
}
